// @algorithm @lc id=40 lang=cpp 
// @title combination-sum-ii


#define print(...)
// @test([10,1,2,7,6,1,5],8)=[[1,1,6],[1,2,5],[1,7],[2,6]]
// @test([2,5,2,1,2],5)=[[1,2,2],[5]]
using iterator_t = vector<pair<int,int>>::iterator;
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<pair<int,int>> dict; // <repeat_times, candidate>
        for(auto d : candidates){
            if(dict.empty() || dict.back().second != d)
                dict.push_back({1, d});
            else
                dict.back().first ++;
        }
        vector<vector<int>> ans;
        vector<int> cb;
        function<void(int,vector<int>&,iterator_t)> dfs
            = [&](int sum, vector<int>& cb, iterator_t it){
            if(0 == sum){
                ans.push_back(cb);
                return;
            }
            if(it == dict.end()) return;
            dfs(sum, cb, it+1);
            const int times = min(sum/it->second, it->first);
            if(times <= 0) return;
            for(int i=1; i<=times; i++){
                if(sum - it->second >= 0){
                    cb.push_back(it->second);
                    print("sum=", sum-it->second*i, "|", cb, "\n")
                    dfs(sum-it->second*i, cb, it+1);
                }
            }
            for(int i=0; i<times; i++)
                cb.pop_back();
        };
        dfs(target, cb, dict.begin());
        return ans;
    }
};